package main

import (
	"fmt"
	"runtime"
	"sync"
)

// 希尔排序的多线程排序
func ShellSortGoRoutine(arr []int) {
	if len(arr) < 2 || arr == nil {
		return // //数组为空或者数组只有1个元素无需排序
	} else {
		wg := sync.WaitGroup{}     // 等待多线程
		cpuNum := runtime.NumCPU() //返回cpu 核数

		// 压缩空间

		for gap := len(arr) / 2; gap > 0; gap = gap / 2 {
			wg.Add(cpuNum)
			ch := make(chan int, 100)
			go func() {
				// 管道写入
				for k := 0; k < gap; k++ {
					ch <- k
				}

				close(ch)
			}()
			for k := 0; k < cpuNum; k++ {
				go func() {
					for v := range ch {
						ShellSortStep(arr, v, gap) // 完成一个步骤的排序
					}
					wg.Done() //  一直等待
				}()

			}
			wg.Wait()
		}

		fmt.Println(arr)
	}
}

//无法理解 希尔排序， 排着 。最后数据乱了 .而后在进行的排序，数据很不稳定
// 数据不能稳定， 大在后，小在前
func ShellSortStep(arr []int, start int, gap int) {
	fmt.Println(gap, "==", start)

	length := len(arr)                           //数组长度
	for i := start + gap; i < length; i += gap { //插入排序的变种
		backup := arr[i] //备份插入的数据
		j := i - gap     //上一个位置循环找到位置插入
		for j >= 0 && backup < arr[j] {
			arr[j+gap] = arr[j] //从前往后移动
			j -= gap
		}
		arr[j+gap] = backup //插入

	}
	// fmt.Println("")

	fmt.Println(arr)
}

func ShellSort(arr []int) []int {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr //一个元素的数组，直接返回
	} else {
		gap := length / 2
		for gap > 0 {
			for i := 0; i < gap; i++ { //处理每个元素的步长
				ShellSortStep(arr, i, gap)
			}
			//gap-- //gap--
			gap /= 2
		}

	}

	return arr
}

func main() {
	// arr := []int{3, 59, 4, 2, 9}

	arr := []int{3, 59, 18, 4, 28, 2, 9, 6, 78, 13, 16, 22}

	fmt.Println(arr)

	// ShellSortStep(arr, 0, 1) // 直接调用最后一步

	// ShellSort(arr)

	ShellSortGoRoutine(arr)

	fmt.Println("")

	// fmt.Println(ShellSort(arr))

}
